import java.util.Scanner;
public class Test {
    public static void main(String[] args) { //汉诺塔问题——递归实现
        hanoi(1,'A','B','C');
        System.out.println();
        hanoi(2,'A','B','C');
        System.out.println();
        hanoi(3,'A','B','C');
        System.out.println();

    }
    public static void hanoi(int n,char pos1,char pos2,char pos3) {
        if(n==1) {
            move(pos1,pos3);
        }
        else {
            hanoi(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hanoi(n-1,pos2,pos1,pos3);
        }
    }
    public static void move(char pos1,char pos2) { //打印过程
        System.out.print(pos1+"->"+pos2+"  ");
    }
    public static void main9(String[] args) {
        //int[] array = new int[]{2,6,4,1};
        int[] array = new int[]{1,2,34,3,4,5,7,23,12};
        boolean ret = find9(array);
        System.out.println(ret);
    }
    public static boolean find9(int[] array) {
        for (int i = 0; i < array.length - 3; i++) {
            if (array[i] % 2 == 1 && array[i + 1] % 2 == 1 && array[i + 2] % 2 == 1) {
                return true;
            }
        }
        return  false;
    }

    public static void main8(String[] args) {
        //int[] array = new int[]{3,2,3};
        int[] array = new int[]{2,2,1,1,1,2,2};
        int ret = find8(array);
        System.out.println(ret);
    }
    public static int find8(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int key=array[i];
            int count = 0;
            for (int j = 0; j < array.length; j++) {
                if(array[j] == key) {
                    count++;
                }
            }
            if(count > (array.length/2)) {
                return array[i];
            }
        }
        return -1;
    }
    public static void main7(String[] args) {
        //int[] array = new int[]{2,2,1};
        int[] array = new int[]{4,1,2,1,2};
        int ret = find_once(array);
        System.out.println(ret);
    }
    public static int find_once(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int key=array[i];
            int count = 0;
            for (int j = 0; j < array.length; j++) {
                if(array[j] == key) {
                    count++;
                }
            }
            if(count == 1) {
                return array[i];
            }
        }
        return -1;
    }
    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入要找的目标：");
        int target = scanner.nextInt();
        int[] array = new int[]{2,7,11,15};
        String ret = find1(array,target);
        System.out.println(ret);
    }
    public static String find1(int[] array,int n) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[i]+array[j] == n) {
                    return "["+i+" "+j+"]";
                }
            }
        }
        return "[]";
    }
    public static void main5(String[] args) {  //二分查找
        Scanner scanner = new Scanner(System.in);
        int[] array = new int[]{1,2,3,4,5,6,7,8,9,10};
        System.out.println("请输入你要查找的数字：");
        int key = scanner.nextInt();
        int ret = find(array,key);
        if(ret == -1){
            System.out.println("找不到!");
        }else{
            System.out.println("找到了，它的下标为："+ret);
        }
    }
    public static int find(int[] array,int n) {
        int left = 0;
        int right = array.length-1;
        while(left <= right) {
            int mid = (left + right)/2;
            if(array[mid] < n) {
                left = mid+1;
            }else if(array[mid] > n) {
                right = mid-1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    public static void main4(String[] args) {
        int[] array = new int[]{1,2,3,4,5,6,7,8,9,10};
        fun(array);
        for (int i = 0; i < 10; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    public static void fun(int[] array) { //奇数放在前面，偶数放在后面
        int left=0;
        int right=array.length-1;
        while(left<right) {
            while((left <right) && (array[left] % 2 == 1)) { // 找偶数
                left++;
            }
            while((left <right) && (array[right] % 2 == 0)) {  //找奇数
                right--;
            }
            if(left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }
    public static void main3(String[] args) {  //数组元素扩大二倍
        int[] array =new int[]{1,2,3};
        transform(array);
        for (int i = 0; i < 3; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    public static void transform(int[] array) {
        for (int i = 0; i < 3; i++) {
            array[i]*=2;
        }
    }
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        int x = fib(n);
        System.out.println(x);
    }
    public static int fib(int n) { //计算斐波那契数列第N项  迭代法
        if(n == 1 || n == 2) {
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
        while(n>2) {
            f3=f1+f2;
            f1=f2;
            f2=f3;
            n--;
        }
        return f3;
    }
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        print(n);//打印每一位数
        //int ret =sum(n); //计算所有位数之和
        //System.out.println(ret);
    }
    public static int sum(int n) {
        if(n>9) {
            return n%10+sum(n/10);
        }
        else return n;
    }

    public static void print(int n) {
        if(n>9) {
            print(n/10);
        }
        System.out.print(n%10);
    }
}
